package review;

import java.util.Arrays;

/**
 * @author 郝文雪
 * @date 2022/7/24 16:20
 * @Description Test
 */
public class heapSort {
    public static void heapSort(int[] arr){
        for(int i=(arr.length-1-1)/2;i>=0;i--) {
            siftDown(arr, i, arr.length);
        }
        for(int i=arr.length-1;i>0;i--){
            swap(arr,0,i);
            siftDown(arr,0,i);
        }
    }

    private static void siftDown(int[] arr, int l, int n) {
        while((l*2)+1<n){
            int j=l*2+1;
            if(j+1<n && arr[j+1]>arr[j]){
                j=j+1;
            }
            if(arr[l]<arr[j]){
                swap(arr,j,l);
                l=j;
            }
            if(arr[l]>arr[j]){
                break;
            }
        }
    }

    private static void swap(int[] arr, int j, int l) {
        int tmp=arr[l];
        arr[l]=arr[j];
        arr[j]=tmp;
    }

    public static void main(String[] args) {
        int[] arr={2,1,3,4,5};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
